"""
堆排序前传-树
    - 树是一种数据结构   比如：目录结构
    - 树是一种可以递归定义的数据结构
    - 树是由n个节点组成的集合
        - 如果n=0, 那这是一棵空树
        - 如果n>0, 那存在1个节点作为树的根节点，其他节点可以分为m个集合, 每个集合本身又是一棵树。
    - 一些概念
        - 根节点、叶子节点
        - 树的深度（高度）
        - 树的度    # 看哪个节点的分叉最多，代表整个树的度
        - 孩子节点/父节点
        - 子树
堆排序前传- 二叉树
    - 二叉树：度不超过2的树
    - 每个节点最多有两个孩子节点
    - 两个孩子节点被区分为左孩子节点和右孩子节点

    - 满二叉树：一个二叉树, 如果每一个层的结点数都达到最大值, 则这个二叉树就是满二叉树

    - 完全二叉树： 叶子节点只能出现在最下层和次下层, 并且最下面一层的结点都集中在该层最左边的若干位置的二叉树

堆排序前传- 二叉树的存储方式
    - 二叉树的存储方式（表示方式）
        - 链式存储方式
        - 顺序存储方式

二叉树中父节点和左孩子节点的编号下标有什么关系 ---> i = 2i + 1
二叉树中父节点和左孩子节点的编号下标有什么关系 ---> i = 2i + 2

堆： 一种特殊的完全二叉树结构
    - 大根堆： 一棵完全二叉树,  满足任一节点都比其孩子节点大
    - 小根堆： 一颗完全二叉树,  满足任一节点都比其孩子节点小

堆的排序过程
    - 建立堆
    - 得到堆顶元素, 为最大元素
    - 去掉堆顶, 将堆最后一个元素放到堆顶, 此时可通过一次调整重新使堆有序
    - 堆顶元素为第二大元素
    - 重复步骤3, 直到堆变空
"""

from SortingAlgorithm.cal_time.cal_time import cal_time


def sift(li, low, high):
    """
    这个调整的过程时间复杂度为：O(logn)
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    """
    i = low        # i最开始指向根节点
    j = 2 * i + 1  # j开始是左孩子
    tmp = li[low]  # 把堆顶存起来
    while j <= high:
        if j + 1 <= high and li[j+1] > li[j]:  # 如果右孩子有并且比左孩子大
            j = j + 1  # j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j      # 往下一层来进行调整
            j = 2 * i + 1
        else:          # tmp更大,把tmp放到i的位置上
            li[i] = tmp   # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp   # 把tmp放到叶子节点上


@cal_time(name="堆排序时间")
def heap_sort(li):
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        # i表示建堆的时候调整的部分的根的下标
        sift(li, i, n-1)
    # 上面的for循环完了，堆就构造完了
    for i in range(n-1, -1, -1):
        # i指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        sift(li, 0, i-1)  # i-1是新的high


if __name__ == "__main__":
    li = [i for i in range(10000)]
    import random
    random.shuffle(li)
    # print(li)

    heap_sort(li)

    # print(li)
